package TreeNodeSecond.SwordOffer;

import java.util.ArrayList;
import java.util.List;

public class FindTarget {
    /**
     * 剑指 Offer II 056. 二叉搜索树中两个节点之和
     * 给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
     * 示例 1：
     * 输入: root = [8,6,10,5,7,9,11], k = 12
     * 输出: true
     * 解释: 节点 5 和节点 7 之和等于 12
     * 示例 2：
     * <p>
     * 输入: root = [8,6,10,5,7,9,11], k = 22
     * 输出: false
     * 解释: 不存在两个节点值之和为 22 的节点
     *
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget(TreeNode root, int k) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        dfs(root, arrayList);
//        int size = arrayList.size();
//        int right = size - 1;
//        //双指针
//        for (int left = 0; left <= size - 1 && left >= right; ) {
//            int sum = arrayList.get(left) + arrayList.get(right);
//            if (sum == k) {
//                return true;
//            } else if (sum > k) {
//                right--;
//            } else {
//                left++;
//            }
//        }
//        return false;
//        int size = arrayList.size(), left = 0, right = size - 1;
//        while (left < size) {
//            for (int i = right; i > left; i--) {
//                int sum = arrayList.get(left) + arrayList.get(i);
//                if (sum == k) {
//                    return true;
//                } else if (sum < k) {
//                    break;
//                }
//            }
//            left++;
//        }
//        return false;
        int left = 0;
        int right = arrayList.size() - 1;
        while (left < right) {
            int sum = arrayList.get(left) + arrayList.get(right);
            if (sum == k) {
                return true;
            } else if (sum > k) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }

    /**
     * 中序遍历，因为是二叉排序树，所以List里面的数据是按照从小到大排序好的
     *
     * @param treeNode
     * @param arrayList
     */
    public static void dfs(TreeNode treeNode, List<Integer> arrayList) {
        if (treeNode == null) {
            return;
        }
        dfs(treeNode.left, arrayList);
        arrayList.add(treeNode.val);
        dfs(treeNode.right, arrayList);
    }
}
